#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/6/26 14:48
# ===========================================
#       题目名称： 53. 最大子数组和
#       题目地址： https://leetcode.cn/problems/maximum-subarray/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:

    def maxSubArray(self, nums):
        max_sum, cur_sum = nums[0], 0  # 定义最大值 和当前sum值
        for index in range(len(nums)):
            num = nums[index]
            if cur_sum > 0:
                cur_sum += num
            else:
                cur_sum = num
            max_sum = max(max_sum, cur_sum)
        return max_sum


if __name__ == '__main__':
    s = Solution()
    # 6
    print("nums = [-2,1,-3,4,-1,2,1,-5,4] => %d" % s.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    # 1
    print("nums = [1] => %d" % s.maxSubArray(nums=[1]))
    # 23
    print("nums = [5,4,-1,7,8] => %d" % s.maxSubArray(nums=[5, 4, -1, 7, 8]))
